1. Field of the Invention
The present invention relates generally to network communications, such as communications in wireless ad-hoc networks. More particularly, the present invention relates to a method, system and apparatus for increasing network security and reliability by excising a compromised router from an ad-hoc network.
2. Background and Related Art
Wireless ad-hoc networks preferably do not rely on immobile base stations or other fixed infrastructure. Accordingly, ad-hoc networks are important in military, emergency, mobile and temporary environments (e.g., business meetings, campaign headquarters, and so forth). As will be appreciated by those of ordinary skill in the art, in some ad-hoc networks, each node is responsible for routing “packets,” or message signals, for other network nodes. An example of this type of network 100 is shown in FIG. 2a. As illustrated, node X can route packets between nodes W, Y and Z, for example. Nodes in an ad-hoc network preferably employ known routing techniques to accomplish their routing requirements.
For example, as discussed in U.S. Pat. No. 6,028,857, issued to R. Poor on Feb. 22, 2000, and assigned to the Massachusetts Institute of Technology, in a “link state” routing approach, each network node maintains a routing table that specifies an “optimal” path toward each network destination. In the U.S. Pat. No. 6,028,857, the term “optimal” is used to generally mean the shortest path, but may account for other factors such as load balancing. As will be appreciated by those skilled in the art, a shortest-path calculation can be performed via a shortest-path first algorithm, for example, Dijkstra's algorithm as explained in Chapter 5 of “Routing in Communications Networks,” M. Steenstrup, ed., 1995.
As discussed in the U.S. Pat. No. 6,028,857, when a node in a link state routing system transmits a message to a destination node, it first fetches from a routing table an entry for the specified destination. The routing table entry specifies which neighbor of an originating node should relay the message and the identification of that neighbor is installed in a message header as the recipient. The originating node then transmits the message. Many of the originating node's nearby neighbors receive the message, since radio frequency (“RF”) transmissions are essentially omni-directional. However, of all the neighbors that receive the transmission, only the specified recipient acts on the message. The recipient relays the message in the same manner, according to an entry in its routing table corresponding to the destination node. This process continues until the message reaches the ultimate destination. The nodes in the U.S. Pat. No. 6,028,857 do not maintain these types of routing tables, but rather maintain “cost tables” that indicate the costs of transmission to other nodes in the network.
Other forms of ad-hoc wireless networks simplify routing and minimize routing traffic by organizing nodes (e.g., network members) into hierarchical groups called clusters, with each cluster having a cluster head. A cluster may include a single cluster head and zero or more cluster members. A cluster head serves as a router for affiliated cluster members. Cluster head stations communicate with each other to form a network backbone, and cluster member stations relay messages to the network through affiliated cluster heads. In mobile systems, cluster members move into and out of clusters depending on their physical location and radio connectivity. An example of this type of mobile communications network 110 is shown in FIG. 2b, in which areas 1a, 1b and 1c represent individual clusters. In FIG. 2b, a double-circle indicates a Cluster Head (“CH”), whereas a single circle indicates a Cluster Member (“CM”). In the FIG. 2b example, CM2 and CM3 are affiliated with a cluster headed by CH1, and CM6 and CM7 are affiliated with a cluster headed by CH5. CH4 is the head of its own cluster.
Another example of a mobile communications network is disclosed in U.S. Pat. No. 5,850,592, issued to S. Ramanathan on Dec. 15, 1998, and assigned to the same assignee of this present application. The 5,850,592 discloses a method for a plurality of mobile stations to automatically organize themselves into a hierarchical network, in which some of the stations operate as message gateways for a cluster of mobile stations. Initially, mobile stations search for available cluster heads and initiate an affiliation procedure to establish themselves as cluster members. If the affiliation procedure is successful, a mobile station operates as a cluster member. Otherwise, a mobile station promotes itself to operate as a cluster head.
In the arrangement of the U.S. Pat. No. 5,850,592, each station operates in at least two basic modes. In the first mode, the mobile station serves as a message gateway or router for a cluster of other member stations. The second mode allows the mobile station to operate as a non-gateway (or “cluster member”) station. Each mobile station determines which out of the two modes to operate in, as discussed above. The mobile stations disclosed in the U.S. Pat. No. 5,850,592 can operate at two different power levels. When there are no other available cluster heads, a mobile station operates as a cluster head, and transmits at a relatively high power level. A cluster head transmits at the relatively high power level to communicate with other cluster head stations and to typically provide longer distance network links. Although a cluster head communicates at a higher power level with other cluster heads, a cluster head can still communicate with its cluster members using a relatively lower power level.
As will also be understood by those of ordinary skill in the art, there are many other known procedures for routing messages over a network, even when a configuration of the network may change. Link state routing is only one well-known routing mechanism. There are also many procedures for measuring or rating the connectivity of a network in a particular configuration (e.g., metric generation) that are well known in the art. These types of techniques will not be described in further detail, however, reference may be had to technical articles including: “Packet Radio Routing,” by Gregory S. Lauer in Chapter 11 of “Routing in Communication Networks,” ed. Martha E. Steenstrup, Prentice-Hall 1995; “Packet Radio Network Routing Algorithms: A Survey,” by J. Hahn and D. Stolle, IEEE Communications Magazine, Vol. 22, No. 11, November 1984, pp. 41-47; “The Organization of Computer Resources into a Packet Radio Network,” by R. E. Kahn, IEEE Trans. on Communications, Vol. COM-25, No. 1, January 1977, pp. 169-178; “Analysis of Routing Strategies for Packet Radio Networks,” J. Garcia Luna Aceves and N. Shacham, Proc. of the IEEE INFOCOM '85, Washington, D.C., March 1985, 292-302; and “The DARPA Packet Radio Network Protocols,” by J. Jubin and J. Tornow, Proc. of the IEEE, Vol. 75, No. 1, January 1987, pp. 21-32. See also U.S. Pat. Nos. 4,718,002, 5,243,592, 5,850,592, 5,881,246, 5,913,921 and 6,028,857 for the general state of the art in wireless network message routing.
As will be appreciated by those of ordinary skill in the art, in wireless ad-hoc networks, all of the nodes are preferably equipped with communications transceivers. At least some of these nodes are capable of network routing functions (“routers”) and the other nodes are merely sources or destinations for data traffic (“endpoints”). Preferably, all nodes in an ad-hoc network execute a set of algorithms, and perform a set of networking protocols. As will be appreciated by those skilled in the art, these algorithms and protocols enable the nodes to find each other, determine paths through the network for data traffic from source to destination(s), and detect and repair ruptures in the network as nodes move, as they fail, as battery power changes, as communications path characteristics change over time, and so forth. It will also be appreciated that network nodes can send “updates” or other messages that supply network information. An update can contain information regarding a router's neighbors, potential neighbors, link metric data (e.g., a “cost” of transmissions or links), affiliated nodes, network conditions, partition information, etc.
Despite the many advantages that are provided by these types of networks, there are still problems to be solved. For example, all networks suffer from security problems to some extent, but ad-hoc networks are more vulnerable in a particular way. That is, an “enemy” may physically obtain possession of one of the routers while it is still functioning as part of an ad-hoc network. The enemy may then manipulate the router (e.g., by reconfiguring or reprogramming it, or even by clever manipulation of its external interfaces) in such a way that the router begins to damage the operation of the rest of the network. A network loses an ability to trust its member routers when an enemy seizes one of the routers. As will be appreciated, all routers in a network must “trust” each other in order for the network to function properly.
These types of problems are not adequately addressed in the art. Thus, there is a need to increase the security and reliability of such ad-hoc networks. There is another need to provide a system and method to excise one or more routers from a functioning ad-hoc network. There is another need to provide a mechanism for reinstating an excised router.